package cn.edu.xjtu.work.searchInsert;

/**
 * 35. 搜索插入位置
 * 
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 */
public class Solution {
  public static void main(String[] args) {
    int[] nums = new int[] { 1, 3, 5, 6 };
    System.out.println(searchInsert(nums, -1));
  }

  public static int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }

  /**
   * 二分查找
   * 
   * @param nums
   * @param target
   * @return
   */
  public static int searchInsert1(int[] nums, int target) {
    if (nums.length == 0) {
      return 0;
    }
    return search(0, nums.length - 1, nums, target);
  }

  public static int search(int left, int right, int[] nums, int target) {
    int mid = (left + right) / 2;
    if (target == nums[mid]) {
      return mid;
    }
    if (left == right) {
      if (target < nums[left]) {
        return left;
      } else {
        return left + 1;
      }
    }
    if (target > nums[mid]) {
      return search(mid + 1, right, nums, target);
    } else {
      return search(left, mid, nums, target);
    }
  }
}
